本发明提供一种适用于移动无线传感器网络的协作节能路由图构造方法,包含:节点寻找两个邻居节点,此三个节点构成的三角形的外接圆内不含有其他节点;该节点的局部路由图保留属于上述三角形的链路边;将所有节点各自的局部路由图组合成一个全网络的路由图;根据上述全网络路由图,由各链路边中垂线组成一个对偶图。本发明的优点在于,路由图恢复方法将路由图的更新限制在本地局部范围内,节点只需要同有关邻居节点交换信息就可以完成路由图的恢复重构工作,减小了网络信息传播的耗能,节约了网络通信带宽资源。
1.一种适用于移动无线传感器网络的协作节能路由图构造方法,其 特征在于,包含: 节点遍历寻找两个邻居节点,此三个节点构成的三角形的外接圆内 不含有其他节点; 该节点的局部路由图保留属于上述三角形的链路边; 将所有节点各自的局部路由图组合成一个全网络的路由图; 根据上述全网络路由图,由各链路边中垂线组成一个对偶图。
2.根据权利要求1所述的一种路由图构造方法,其特征在于,所述 寻找两个邻居节点的过程进一步包含:各节点等待一个随机退避时间Ti, 随后广播各自的身份标识和位置信息,并转发得到的邻居信息。
3.根据权利要求1所述的一种路由图构造方法,其特征在于,当节 点发生移动时,进一步包含: 运动节点将自身更新的位置和通信半径信息发送给所有邻居节点; 收到信息的外围节点将运动节点的位置信息转发给将落入所述运动 节点通信半径之内的邻接节点; 所述邻接节点计算出与运动节点的连接时间; 当所述邻接节点进入运动节点通信半径内,发送信息到运动节点来 初始化通信; 运动节点断开与离开通信半径范围的外围节点的连接。 技术领域 本发明涉及一种适用于无线传感器网络中节点存在移动性环境的协 作式节能路由协议方法,尤其涉及一种适用于移动无线传感器网络的协 作节能路由图构造方法。 背景技术 近年来,随着微机电系统(MEMS-Micro-Electro-Mechanismxa0System)、 无线通信、信息网络与集成电路等技术的迅速发展,新兴的无线传感器 网络(WSN-Wirelessxa0Sensorxa0Networks)应运而生。无线传感器网络由部署 在监测区域内的低成本微型传感器节点组成。节点的部署可通过飞行器 撒播、人工放置和火箭弹射等方式完成。这些节点通过无线通信方式形 成多条自组织的网络系统,相互协同地感知、采集和处理网络覆盖地理 区域中目标的信息。最终,目标信息通过网络进行路由选择后传送给指 令中心节点。用户可以直接或通过互联网间接向WSN发送目标查询命 令,获得相关目标信息。 网络中的每个节点都含有若干体积小、价格便宜、低能耗的多功能 传感器和其他组件。每个传感器节点可具备信号采集、数据处理、相互 通信的功能,并直接嵌入到相应的设备或环境当中,具有很强的灵活性 和移动性。因此,集成了网络技术、嵌入式技术及传感器技术的无线传 感器网络大大扩展了人们的信息获取能力,将逻辑上的信息世界与真实 的物理世界融合在一起,可以为人们提供最直接,最有效,最真实的信 息。利用WSN可实现数据的采集量化、处理融合和传输应用,并可以广 泛地应用在数字家庭、医院、军事、环境监测及工业控制等领域。 路由协议负责将数据分组从源节点通过网络转发到目的节点,它主 要包括两个方面的功能:寻找源节点和目的节点间的优化路径;将数据 分组沿着优化路径正确转发。在无线传感器网络中,节点能力一般认为 是有限的且一般没有能量补充,因此路由协议需要高效利用能量;同时 传感器网络节点数目往往比较巨大,节点由于通信距离限制只能获得局 部拓扑信息,设计的路由协议要能在局部网络信息的基础上选择合适的 路径。 无线传感器网络通常由大量密集的传感节点构成,网络中节点的能 量资源、计算能力和带宽都非常有限,这就决定了无线传感器网络协议 栈各层的设计都必须以能源有效性为首要的设计要素。具体到网络层设 计,主要目标是:能源有效性路径的建立;可靠数据转发机制的形成; 最长网络生命周期的实现。 无线传感器网络路由协议设计与传统的无线adxa0hoc网络有很多不 同,无线传感器网络路由设计的重要目标是降低节点能源损耗,提高网 络生命周期;而传统的无线adxa0hoc网络的路由协议设计的首要任务是移 动条件下高服务质量的提供。设计目标的不同导致了传统的无线adxa0hoc 网络路由协议不能直接应用于无线传感器网络中。因此,设计新的适用 于无线传感器网络的路由协议已经成为无线传感器网络研究的重点课 题。 根据现有无线传感器网络路由协议实现方法的特点,可将它们大致 分为四类:洪泛式路由协议,层次式路由协议,以数据为中心的路由协 议,以及基于位置信息的路由协议。几乎所有的无线传感器网络路由协 议都可归为这四类。 1、洪泛式路由协议:这种协议是一种旧式的协议,它不需要维护网 络的拓扑结构和路由计算,接收到消息的节点以广播形式转发数据包给 所有的邻节点。对于自组织的传感器网络,洪泛式路由是一种较直接的 实现方法,但容易带来消息的“内爆”和“重叠”,而且它没有考虑能 源方面的限制,具有“资源盲点”的缺陷。 2、层次式路由协议:它的基本思想是将传感节点分簇,簇内通信由 簇头节点来完成,簇头节点进行数据聚集和合成,最后簇头节点把聚集 的数据传送给终端节点。这种方式可以减少信息传输量,能满足传感器 网络的可扩展性,同时可以有效的维持传感器节点的能量消耗,从而延 长网络生命周期。 3、以数据为中心的路由协议:它的基本思想是对传感器网络中的数 据用特定的描述方式命名,数据传送基于数据查询并依赖数据命名,按 照对感知数据的需求、数据通信模式和流向等,以数据为中心形成信息 的转发路径。这种方式的通信不再依赖特定的节点,而是依赖于网络中 的数据,减少在网络中大量传送重复冗余数据,从而延长网络生命周期。 4、基于位置信息的路由协议:它利用节点的位置信息,把查询信息 或者数据转发给需要的地域,从而缩减数据的传送范围。实际上许多传 感器网络的路由协议都假设节点的位置信息为已知,所以可以方便的利 用节点的位置信息将节点分为不同的域。基于域进行数据传送能缩减传 送范围并减少中间节点,从而延长网络生命周期。 当无线传感器网络中节点全部以最大发射功率通信时,全网络形成 一个由所有节点(V={v1,v2,...,vn})以及通信链路边(E)构成的通信网 络图,记为原图G=(V,E)。但是,实际无线传感器网络在转发数据时, 往往各节点会以小于最大功率的一定功率相互通信,并且根据一定的选 路规则选择部分路径组成一个全网形式的通信图,称为路由图,该路由 图为原图的子集/图。路由图是无线传感器网络路由协议运行的基础和路 径选择的信息库。节点将数据分组从源节点通过网络转发到目的节点的 过程中,在每个中间节点进行通信链路选择时都是选择属于路由图中的 一段链路。 目前,无线传感器网络越来越多的出现了存在移动性需求的应用环 境,例如传感器节点本身具有移动性,传感器节点被放置在移动性的环 境中等情况。移动性的出现给网络路由协议特别是数据分组转发路径的 选择带来了很大的困难,主要体现为路由协议路由图拓扑不断发生变化。 如何高效动态的构造移动环境下无线传感器网络路由图是路由协议有效 节能的关键和核心问题。 发明内容 本发明的目的在于,提供一种适用于无线传感器网络中节点存在移 动性环境的协作式节能路由协议方法,本发明主要涉及路由协议中如何 有效构造路由图的内容。发明针对移动无线传感器网络自身的特点,通 过设计合理的路由图和路由选择方法,使得无线传感器网络可以在网络 中出现节点移动的情况下,各节点只需邻居节点信息就可以在全网络有 效地构造路由图并找到高效的路由转发策略,最终节约整个网络的能量。 本发明解决技术问题所采用的技术方案为: 一种适用于移动无线传感器网络的协作节能路由图构造方法,包含: 节点遍历寻找两个邻居节点,此三个节点构成的三角形的外接圆内不含 有其他节点;该节点的局部路由图保留属于上述三角形的链路边;将所 有节点各自的局部路由图组合成一个全网络的路由图;根据上述全网络 路由图,由各链路边中垂线组成一个对偶图。 所述寻找两个邻居节点的过程进一步包含:各节点等待一个随机退 避时间Ti,随后广播各自的身份标识和位置信息,并转发得到的邻居信 息。 当节点发生移动时,进一步包含:运动节点将自身更新的位置和通 信半径信息发送给所有邻居节点;收到信息的外围节点将运动节点的位 置信息转发给将落入所述运动节点通信半径之内的邻接节点;所述邻接 节点预先计算出与运动节点的连接时间;当所述邻接节点进入运动节点 通信半径内,发送信息到运动节点来初始化通信;运动节点断开与离开 通信半径范围的外围节点的连接。 本发明的优点在于,所述路由图恢复方法将路由图的更新限制在本 地局部范围内,节点只需要同有关邻居节点交换信息就可以完成路由图 的恢复重构工作,减小了网络信息传播的耗能,节约了网络通信带宽资 源。 附图说明 图1为本发明由传感器节点局部路由图组成的全网络路由图; 图2为本发明传感器节点生成路由拓扑图的工作流程图; 图3为本发明传感器节点移动前网络拓扑路由图; 图4为本发明传感器节点移动后网络拓扑路由图; 图5为本发明传感器节点移动过程的工作流程图。 具体实施方式 有关本发明的技术内容及详细说明,现配合附图说明如下: 本发明适用于网络节点组成相同,通常指节点通信能力相同,即有 相同的最大通信半径;节点已被全网络范围分配统一的IP地址或MAC 地址等身份标识,并且各节点通过GPS设备等定位装置可获得自身的位 置信息。 图1为本发明由传感器节点局部路由图组成的全网络路由图。该路 由图是由各节点局部选择的本地路由图组合而成的,本发明的一种适用 于移动无线传感器网络的协作节能路由图构造方法,包含: 1)节点与相邻的两个邻居节点构成一个三角形,该三角形所在外接 圆内不再含有其它节点,该节点局部路由图只保留属于这类三角形的链 路边。2)所有节点各自的本地局部路由图组合在一起,共同组成一个全 网络的路由图,图1虚线部分所示。3)基于上面生成的全网路由图,由 各链路边中垂线再组成一个与路由图对应的对偶图,图1中实线部分所 示。 在本发明中,邻居节点,指位于节点通信半径之内的节点;邻接节 点,指节点所在子区域同运动节点所在子区域相邻的邻居节点;外围节 点,指有邻接节点落在移动节点通信半径之外的邻居节点。定义对偶图 各边所围成的区域为该对偶图的子区域,本发明所述子区域均指对偶图 所划分形成的子区域。各传感器节点所在子区域内的任意一点距离该传 感器节点最近。 图2为本发明传感器节点生成路由拓扑图的工作流程图。由于各节 点刚刚投入使用,并不知道其它邻居节点的相关信息,因此各节点为了 避免相邻节点同时发送信息产生碰撞冲突,首先等待一个随机退避时间 Ti(步骤S101);随后以最大功率广播各自的身份标识和位置信息,并 转发得到的邻居信息(步骤S102),这样,所有节点会获得其邻居节点 的身份标识和位置信息;再判断与相邻的两个邻居节点能否构成一个特 殊三角形(步骤S103),该三角形所在外接圆内不再含有其它节点,若 能,则保留属于这类三角形的链路边,构成节点本地局部路由图(步骤 S104);然后,将所有节点各自的本地局部路由图组合在一起,共同组 成一个全网络的路由图(步骤S105);最后,根据此路由图,由各链路 边中垂线再组成一个与路由图对应的对偶图(步骤S106)。 图3和图4分别为本发明传感器节点移动前后网络拓扑路由图。为 了消除移动节点对网络路由转发拓扑造成的影响,需要对变化了的网络 路由拓扑图进行修复并生成相应新的路由图,具体方案如下: 如图5所示,当节点s发生运动时,它将自身更新的位置和通信半 径信息发送给所有邻居节点(步骤S201),即图3中所示通信半径内所 有节点;若接收到信息的邻居节点是一个外围节点“■”,该外围节点 将检查是否它的邻接节点“●”将会落入运动节点s的通信半径之内(步 骤S202),若会则该外围节点将同时向它的这个邻接节点转发包含运动 节点s位置信息的“预注册”信息(步骤S203)。如此,新的邻居节点 将会预先估算出与运动节点s的连接时间(步骤S204),并会增强协议 路由图恢复的能力,缩短恢复时间。当新的邻居节点进入运动节点通信 半径内,图2所示红色虚线范围内,新的邻居节点发送“通告”信息到 运动节点来初始化通信(步骤S205)。运动节点同样也断开同任何离开 通信半径范围的外围节点的连接(步骤S206)。某些节点可能同时是运 动节点的邻接节点和外围节点,这并不影响本发明上述操作的实施,同 时属于两类节点就同时执行各自类型节点要求的操作。 如图4所示,当运动节点s下一个时刻运动到三角形位置时,网络 可以迅速的生成一个新的路由图拓扑,整个网络继续根据新的路由拓扑 图进行路由转发操作。 上述仅为本发明的较佳实施例而已,并非用来限定本发明实施范 围。即凡依本发明申请专利范围所做的均等变化与修饰,皆为本发明专 利范围所涵盖。